Binary codes transmitted through a transmission line are subject to being changed by various noise signals or disturbances causing random errors and/or burst errors before they are received and passed to a decoder. With a view to eliminating such errors from binary codes, various methods have already been proposed.
It is known that the Bose-Chandhuri-Hocquenghem Code (BCH) is one of the random error correcting codes. Relevant art may include "Error Correcting Codes" by W. W. Peterson, The M.I.T. Press, Cambridge, Mass., John Wiley, New York, 1961; "Algebraic Coding Theory" by E. R. Berlekamp, The M.I.T. Press, Cambridge, Mass. John Wiley, New York, 1968; and "A Method for Solving Key Equation for Decoding Goppa Codes" by Y. Sugiyama et al., Information and Control, Vol. 27, pp 87-99, 1975.
FIG. 1 is a block diagram of a cyclic error locating unit based on theory set forth in the above mentioned Peterson article. An error correction process of this cyclic error locating unit may be comprised in following three steps.
(a) A received vector r(X)=r.sub.0 +r.sub.1 X+r.sub.2 X.sup.2 + . . . +r.sub.n-1 X.sup.n-1 applied to an input terminal 1 is sent to a syndrome calculator 2 producing syndrome S=S.sub.1, S.sub.2, . . . , S.sub.2t. PA0 (b) Results of step a are sent to a logic circuit 3 in order to find an error location polynominal .sigma.(X). PA0 (c) Error location numbers .beta..sub.i are determined by finding a root of .sigma.(X).
The values .sigma..sub.1, .sigma..sub.2, . . . , .sigma..sub.t for testing error locations determined by such steps are respectively input to the .sigma. registers R.sub.1, R.sub.2, . . . , R.sub.t of the cyclic error location unit 4. Contents of the registers are input to the Galois Field Arithmetic Units (GFAU) M.sub.1, M.sub.2, . . . , M.sub.t to be multiplied with root of .sigma.(X). Results of these multiplications are returned to the respective registers. Each output of the register is sent to a logic circuit U.sub.A, which outputs "1" when the sum of them ##EQU1## is equal to 1, otherwise, "0". This output from the circuit U.sub.A is sent to one input of an adder 6. The other input of the adder 6 is connected to a delay buffer 5. The buffer 5 stores the received vector signal sent from the input terminal 1. The bit .gamma..sub.n-1 from the buffer is added to an output of the circuit U.sub.A using the adder 6 to produce an error corrected signal, which is then sent to an output terminal 7.
On the other hand, the Fire code is known as a typical burst error correction code, where P(x) represents a known polynominal of m order, and e represents the least positive integer with X.sup.e +1 to be divisible. The Fire code for correcting a single burst error up to a length of l is generated by a following general polynominal. EQU g(x)=P(x)(1+X.sup.2e-1) (1)
Where l.ltoreq.m, and 2l-1 is not divisible by e. The paper by W. W. Peterson, entitled "Error-Correcting Codes", MIT Press, Cambridge, Mass., New York, 1961 teaches us that the code length n is given by LCM (e, 2l-1). The burst error correcting capability of the Fire code is equal to 2 l/(m+2l-1). The paper by S. Lin, entitled "An Introduction to Error Correcting-Codes," Englewood Cliffs, N.J., Prentice Hall, Inc. also teaches us that .eta. is approximately equal to 2/3, if l=m and m.fwdarw..infin..
When discussing burst error correcting capability, it is known that a limit of burst error correcting capability of (n, k, l) code (register's limit) exists, where l is burst error correcting capability, n is length, and k is a number of symbols in case of burst error correcting code. The code which satisfies l=(n-k)/2 is the most optimum value, where .eta.=1. This indicates that the Fire code is not effective at the register's limit.
Some of the effective cyclic and shortened cyclic codes for correcting single burst error are listed in the following table. There are also described in the above mentioned paper by S. Lin i.e. "An Introduction to Error-Correcting Codes"; pp 119-129.
TABLE ______________________________________ CODE Burst error General n-k-2l (n, k) correcting capability polynomial ______________________________________ 0 (7,3) 1 35 (15,9) 3 171 (15,11) 4 1151 (27,17) 5 2671 (34,22) 6 15173 (38,24) 7 114361 (50,34) 8 224531 (56,38) 9 1505773 (59,39) 10 4003351 1 (15,10) 2 65 (27,20) 3 311 (38,29) 4 1151 (48,37) 5 4501 (67,54) 6 36365 (103,88) 7 114361 (96,79) 8 501001 7 (31,25) 2 161 (63,55) 3 711 (85,75) 4 2651 (131,119) 5 15163 (169,155) 6 55725 3 (63,56) 2 355 (121,112) 3 1411 (164,153) 4 6255 (290,277) 5 24711 4 (511,499) 4 10451 5 (1023,1010) 4 22365 ______________________________________ where, n = Code length k = Number of information digits
FIG. 2 is a block diagram of an error trapping decoder in connection with the theory described in the above mentioned Lin paper. In the first step, the transmitted information digits k coming from the input terminal 1 is passed to a modulo 2 adder 8 to be added with an output from a gate 11. An output from the adder is applied to a syndrome register 9 consisting of shift registers of (n-k) stages, and is also applied to a delay buffer register 5 of k stages. Where, k=5, n=15. In this step, the gate 11 is held in turned ON state, and gates 12 and 13 are held in turned OFF state.
In the second step, the weight bit outputs of register 9 are respectively input to a gate circuit 14 consisting a group of OR gates and its outputs are in turn applied to an all 0's check and control circuit 15. If outputs from circuit 14 are all 0's, the circuit 15 outputs "1", otherwise "0". The former means that the k received information digits in the buffer register 5 are error free. In this case, the gate 13 is turned ON and the k received information digits stored in the register 5 are sent to the output terminal 7 through the adder 5a and gate 13, while the gate 12 is held in turned OFF state.
If the output is in the latter case, the gate 11 is turned ON and the gates 12, 13 are held in turned OFF state and contents of the register 9 are shifted once to the left so that its output is fed back through the line 10.
With such operations, if the weight of the contents of the syndrome register 9 never goes down to 1 or less by the time the k received information digits have been read out of the buffer 5, then either an uncorrectable error pattern has occurred or correctable error pattern with errors not confined to n-k consecutive portion s has occurred.
Finally, the codes for correcting random and burst errors, such as the codes described in the paper entitled "Error-Correcting Code for a Compound Channel" by H. T. Hsu, T. Kasami and R. T. Chien, IEEE Trans. IT-14, No. 1, pp 135-138, 1968 are rather complicated and not effective.